Read the original article here.

---

Okay, here is the detailed educational resource on Real-Time Operating Systems (RTOS), framed within the context of learning to build a computer from scratch.

---

Understanding Real-Time Operating Systems (RTOS)

When building a computer and its foundational software layer – the operating system – understanding different OS paradigms is crucial. While general-purpose operating systems like those on your desktop or phone are designed for user convenience, throughput, and flexibility, another vital category exists: Real-Time Operating Systems (RTOS). These are fundamental to embedded systems, industrial control, robotics, automotive systems, and many other areas where timing isn't just about being fast, but about being predictably fast and meeting deadlines.

What is a Real-Time Operating System?

A Real-Time Operating System (RTOS) is an operating system (OS) specifically designed to process data and events within precise time constraints. Unlike a general-purpose OS, the primary goal of an RTOS is to guarantee a response within a defined, often very short, time limit.

In the context of building a computer from scratch, a general-purpose OS often focuses on sharing resources fairly among many programs (time-sharing). An RTOS, however, is obsessed with predictability and meeting deadlines. If a task must complete within 10 milliseconds, the RTOS is designed to guarantee that it will.

Think about the difference:

• General-Purpose OS (e.g., Linux, Windows): "Get this done as quickly as possible, sharing the CPU nicely with others. If it takes a few extra milliseconds sometimes, that's usually okay." The goal is high throughput (getting a lot of work done overall) and fairness.
• Real-Time OS (RTOS): "Get this done within exactly this specific time window, every single time, even if it means dedicating the CPU to this one task temporarily." The goal is guaranteed timeliness and predictability.

Failure in an RTOS often means a system failure, not just a slow response. Operations must verifiably complete within their time and resource constraints, or trigger a "fail-safe" condition. RTOS are typically event-driven and preemptive, meaning they react quickly to external or internal events and can interrupt a running task if a higher-priority task needs the CPU.

Key Characteristics of an RTOS

The defining features of an RTOS revolve around its handling of time and task execution:

1. Timeliness and Determinism: This is the core. An RTOS aims for deterministic timing, meaning the time taken for a specific operation (like responding to an event) is predictable and repeatable, not just fast on average.

2. Predictability (Low Jitter):

   Jitter: The variability in the time it takes for a task to complete or for a system to respond to an event. High jitter means unpredictable timing; low jitter is crucial for real-time systems.

   An RTOS minimizes jitter. If a task takes 5ms sometimes and 500ms at other times, that high jitter is unacceptable for real-time applications, even if the average is low. An RTOS strives for a consistent execution time.

3. Guaranteed Performance Categories (Hard vs. Soft): RTOS are categorized by the strictness of their timing requirements:

   • Hard Real-Time Operating System (Hard RTOS): Missing a deadline is a critical failure, often with severe consequences. A late answer is a wrong answer.
     • Example: An airbag deployment system in a car. The airbag must deploy within a few milliseconds of detecting a crash. If it deploys late, it's useless or even harmful.
   • Soft Real-Time Operating System (Soft RTOS): Missing a deadline is undesirable but not catastrophic. Performance degrades, but the system doesn't fail completely. A late answer is acceptable, just not ideal.
     • Example: A video streaming application. If a frame of video arrives slightly late, you might see a brief stutter, but the stream continues.

   The chief design goal of any RTOS is guaranteeing performance within a specific category (hard or soft), not necessarily achieving the highest possible overall throughput.

4. Scheduler Flexibility and Efficiency: While often dedicated to a narrower set of applications than general OSes, an RTOS scheduler is highly sophisticated to manage task priorities and deadlines effectively.

5. Minimal Latency: RTOS are optimized for quick responses to events.

   Interrupt Latency: The time between a hardware interrupt signal being generated and the operating system starting to execute the corresponding interrupt service routine (ISR). Thread Switching Latency: The time it takes for the operating system to save the state of the currently running task and load the state of the next task to be run.

   Low interrupt and thread switching latency are paramount in an RTOS because events happen rapidly, and the OS must react and switch between tasks very quickly to meet tight deadlines. An RTOS is valued more for how quickly or predictably it can respond than for the sheer amount of work it can crunch through in a given time (which is a throughput metric).

RTOS Design Philosophies

How an RTOS decides which task runs when is determined by its scheduling philosophy. The two main approaches are:

1. Event-Driven (Preemptive Priority Scheduling): This is the most common approach for RTOS. The OS switches tasks only when a higher-priority event occurs that requires the CPU.

   • Mechanism: Each task is assigned a priority. The scheduler always runs the highest-priority task that is ready to execute. If a low-priority task is running and a higher-priority task becomes ready (e.g., due to an interrupt), the OS preempts (stops) the low-priority task immediately and switches to the high-priority task.
   • Advantage: Ensures that critical, time-sensitive tasks get the CPU when they need it, minimizing response time for high-priority events.
   • Disadvantage: A lower-priority task might get starved of CPU time if high-priority tasks are always ready.

2. Time-Sharing (Round-Robin Scheduling): More typical of general-purpose OSes, but sometimes used in parts of an RTOS or for non-real-time tasks running alongside real-time ones. Tasks are switched based on a regular timer interrupt, giving each task a small slice of CPU time in a rotating fashion.

   • Mechanism: Tasks are placed in a queue. The scheduler runs the first task for a fixed time slice, then moves it to the end of the queue and runs the next task. This cycle repeats. Events can also trigger switches, but the timer is the primary driver.
   • Advantage: Provides a smoother, fairer distribution of CPU time, giving the illusion that multiple tasks are running simultaneously, which is good for user interaction or non-critical background processes.
   • Disadvantage: Switches tasks more often than strictly needed from a priority perspective, increasing overhead. Crucially, it doesn't inherently guarantee that a high-priority task will run immediately when needed if it's not the task next in line in the round-robin sequence (unless combined with preemption, which is common).

Early CPU designs had relatively high overhead for task switching, influencing OS designs to minimize switches. Modern CPUs have reduced this overhead significantly, making preemptive and event-driven approaches more efficient and practical for RTOS requirements.

Task Management and Scheduling

At the heart of any OS, especially an RTOS, is the scheduler, which manages the life cycle of tasks (or threads).

Task (or Thread): A distinct, independent unit of execution within a program. In an OS, tasks are the entities that the scheduler manages and assigns CPU time to.

Tasks in a typical OS design transition through different states:

1. Running: The task is currently executing on the CPU.
2. Ready: The task is able to run (all its requirements are met) but is waiting for the CPU to become available. Ready tasks reside in a queue, often called the "ready queue" or "run queue".
3. Blocked: The task is unable to run because it is waiting for some event to occur (e.g., waiting for I/O completion, waiting for a message, waiting for a mutex to be released). Blocked tasks are not considered by the scheduler until the event they are waiting for occurs, at which point they transition to the Ready state.

In a system with multiple tasks but only one CPU core, only one task can be in the Running state at any given moment. Most tasks will be either Ready or Blocked. The size of the Ready queue depends on the number of active tasks and the scheduler's behavior. In non-preemptive systems (less common for RTOS core tasks), a task runs until it voluntarily gives up the CPU, potentially leading to "resource starvation" for other ready tasks. A key RTOS challenge is managing the Ready queue efficiently.

The data structure used for the Ready queue is critical for performance. In a real-time system, the scheduler's operations (like adding a task to the ready queue or finding the highest-priority task) must be fast and, ideally, have a predictable, low worst-case execution time. This is because the scheduler often runs in a "critical section" where interrupts might be temporarily disabled to protect its internal data structures. The time spent here adds directly to interrupt and dispatch latency.

• Simple Linked List: If the number of ready tasks is always very small, a simple linked list might suffice. However, finding the highest priority task might require traversing the list, which is inefficient if the list grows or isn't sorted.
• Sorted List: A list sorted by priority allows finding the highest priority task quickly (it's always the first). Inserting a new task requires traversing the list to find the correct sorted position. If this insertion process is done within a critical section where preemption is inhibited, it can increase latency. Advanced designs ensure that even during list manipulation for lower-priority tasks, higher-priority tasks becoming ready can still preempt or be quickly inserted.
• Advanced Data Structures: For systems with potentially many tasks, including mixed real-time and non-real-time, structures like priority heaps or more complex multi-level queues (e.g., run queues per priority level) might be necessary to ensure deterministic, fast insertion and extraction of the highest-priority task, even with arbitrarily many ready tasks.

The time it takes for the OS to react to an event that makes a task ready and then switch to the highest priority ready task is a critical metric. This includes the time to queue the new task and the time to perform the context switch to the target task. This combined time is sometimes called the critical response time or flyback time. A well-designed RTOS minimizes this time, aiming for a very small, predictable number of CPU instructions.

Common RTOS Scheduling Algorithms

RTOS employ various sophisticated algorithms to manage the Ready queue and decide which task runs next, prioritizing based on factors like priority, deadline, or frequency:

• Cooperative Scheduling: Tasks voluntarily yield the CPU. Least common for core RTOS tasks due to lack of preemption.
• Preemptive Scheduling: The OS can interrupt a running task.
  • Rate-Monotonic Scheduling (RMS): A fixed-priority algorithm where tasks with higher frequency (shorter period/deadline) are given higher priority. Mathematically proven to be optimal among fixed-priority schemes under certain conditions.
  • Fixed-Priority Preemptive Scheduling (FPPS): The most common RTOS algorithm. Each task has a fixed priority, and the highest-priority ready task always runs. Often implemented with priority levels and a ready queue for each level.
  • Fixed-Priority Scheduling with Deferred Preemption / Non-Preemptive: Variations where tasks can run for a limited time or through critical sections without being preempted by some higher priorities.
  • Critical Section Preemptive Scheduling: Scheduling logic specifically considering critical sections protected by mechanisms like mutexes.
  • Round-Robin Scheduling: (As discussed above) Often used within a priority level in FPPS for tasks of the same priority, or for non-real-time tasks.
  • Static-Time Scheduling: A pre-computed schedule (like a timetable) determines when each task runs. Very deterministic but inflexible.
• Earliest Deadline First (EDF): A dynamic-priority algorithm where the task with the nearest deadline is given the highest priority. Can achieve higher CPU utilization than fixed-priority but is more complex to implement and analyze.
• Stochastic Digraphs with Multi-threaded Graph Traversal: More advanced techniques for complex systems with dependencies and variable execution times.

The choice of algorithm depends heavily on the application's requirements, complexity, and the need for theoretical guarantees vs. implementation simplicity.

Inter-Task Communication and Resource Sharing

Multitasking systems inherently face the challenge of multiple tasks needing access to shared resources, such as data structures, hardware registers, or peripherals. Allowing uncontrolled simultaneous access can lead to data corruption or system instability (race conditions). General-purpose OS methods exist, but RTOS require solutions that are fast and predictable.

Race Condition: A situation where the outcome of program execution depends on the unpredictable order in which multiple tasks are scheduled by the operating system. This typically occurs when tasks access shared resources concurrently without proper synchronization.

There are three primary approaches to managing shared resources in an RTOS context:

1. Temporarily Masking/Disabling Interrupts:

   • Mechanism: On single-processor systems, a task entering a critical section (code that accesses a shared resource) disables hardware interrupts. This prevents the OS scheduler (which is typically activated by a timer interrupt) and other interrupt handlers from running. Since no other code can run while interrupts are disabled, the current task has exclusive use of the CPU and access to shared resources. When it exits the critical section, it re-enables interrupts.
   • Context for "From Scratch": This is the simplest synchronization mechanism to implement at the very low level. It involves directly interacting with the CPU's interrupt controller or status flags.
   • Advantages: Very low overhead (can be just a few CPU instructions). Guarantees exclusive access on a single processor.
   • Disadvantages:
     • Increases interrupt latency for all interrupts that occur while masked. If the critical section is long, important interrupts could be delayed or even missed.
     • Doesn't work on multi-processor systems (disabling interrupts on one core doesn't stop others).
     • Cannot make blocking OS calls (like waiting for I/O) while interrupts are disabled, as this would halt the entire system.
     • General-purpose OSes typically don't allow user-mode code to disable interrupts for security and stability reasons; this method is more common in embedded systems or within the RTOS kernel itself, or in application code running in a privileged mode.
   • Use Case: Best suited for very short critical sections involving simple, fast operations like reading/writing a few variables or accessing bit-mapped hardware registers where different tasks control different bits. The duration of interrupt masking must be less than the maximum acceptable interrupt latency.

2. Mutexes (Mutual Exclusion Objects):

   • Mechanism: A mutex acts like a lock for a shared resource. A task must "acquire" (lock) the mutex before accessing the resource. If the mutex is already locked by another task, the requesting task "blocks" (enters the blocked state) and waits until the mutex is "released" (unlocked) by its current "owner" (the task that locked it). Tasks can often set a timeout when waiting for a mutex.
   • Context for "From Scratch": Implementing mutexes requires OS support – the scheduler needs to manage waiting tasks and wake them up when the mutex is released. This involves system calls and task state transitions, adding overhead compared to simply disabling interrupts.
   • Advantages: Works on multi-processor systems. Doesn't necessarily block all other tasks (only those needing the specific resource or CPU time). Allows tasks to block and wait, enabling more complex synchronization.
   • Disadvantages and Problems:
     • Priority Inversion: A high-priority task (H) needs a mutex locked by a low-priority task (L). H blocks and waits for L. While L holds the mutex, it can be preempted by a medium-priority task (M) that doesn't need the mutex. Now, H (high priority) is effectively blocked by M (medium priority) because L (low priority) cannot run to release the mutex while M is using the CPU. The priority order has been "inverted".
       • Solution (Priority Inheritance): A common technique where, if a high-priority task blocks waiting for a mutex held by a low-priority task, the low-priority task temporarily inherits the priority of the highest-priority task waiting for that mutex. This ensures the low-priority task gets CPU time to finish its critical section and release the mutex quickly, allowing the high-priority task to run. Priority inheritance itself can become complex with multiple nested mutexes.
     • Deadlock: Two or more tasks become permanently blocked, waiting for resources that the others hold. The simplest scenario: Task A locks Mutex 1, then needs Mutex 2. Task B locks Mutex 2, then needs Mutex 1. A waits for B, B waits for A – a cycle occurs, and neither can proceed. Deadlocks are typically prevented through careful design, establishing a consistent order for acquiring multiple mutexes or using timeouts (though timeouts turn a permanent block into a timed failure).

3. Message Passing:

   • Mechanism: Instead of directly accessing a shared resource, tasks communicate by sending messages. One task is designated as the "manager" of the resource. Other tasks wanting to use the resource send a message to the manager task requesting the operation (e.g., "read sensor value", "write data to display"). The manager task receives messages, performs the requested operation on the resource (which only it directly accesses), and may send a response message back.
   • Context for "From Scratch": Requires implementing a message queue mechanism and defining message formats. This adds complexity but encapsulates resource access logic within a single task.
   • Advantages: Can simplify synchronization logic by centralizing resource access. Avoids many of the protocol-level deadlock issues inherent in mutexes (though deadlocks can still occur if tasks wait for response messages cyclically). Often considered better-behaved than semaphore/mutex systems in complex scenarios.
   • Disadvantages: Can have less "crisp" real-time behavior compared to direct mutex access or interrupt disabling, as it involves queuing messages and task scheduling overhead.
   • Problems:
     • Priority Inversion: Can occur if the manager task processes messages in the order they arrive (e.g., FIFO) rather than by the priority of the requesting task. A low-priority message being processed can block a high-priority task waiting for a response to its message.
     • Protocol Deadlock: Can occur if tasks wait indefinitely for response messages from each other, creating a dependency cycle.

Understanding and correctly implementing synchronization mechanisms is one of the most challenging but essential aspects of building a reliable multitasking OS, especially an RTOS where correctness depends on timely execution despite concurrency.

Interrupt Handlers and the Scheduler

Hardware interrupts (like a timer tick, a network packet arriving, or a button press) are fundamental to event-driven systems. When an interrupt occurs, the CPU pauses the currently running task and jumps to a special piece of code called an Interrupt Service Routine (ISR) or Interrupt Handler.

In an RTOS, interrupt handlers are typically designed to be extremely short.

Interrupt Service Routine (ISR) / Interrupt Handler: A special function executed by the CPU in response to a hardware interrupt. It is designed to handle the immediate needs of the interrupting device and then return control quickly.

• Why keep Handlers short? While an interrupt handler is running, it often has very high privilege, and in some cases, the OS scheduler might be temporarily locked or other interrupts disabled (depending on architecture and priority levels). This adds to the system's interrupt latency. Since RTOS must minimize latency, handlers do the bare minimum:
  1. Acknowledge the interrupt with the hardware.
  2. Signal a task that work needs to be done. This is often done by unblocking a specific task (like a device driver task) using an OS mechanism (e.g., releasing a semaphore, sending a message, or setting a flag that the task is waiting on).
  3. Exit the handler quickly.

The actual processing of the event (e.g., reading data from a buffer, performing calculations) is deferred to a regular task, which runs under the control of the scheduler and can be preempted if a higher-priority task becomes ready. The RTOS scheduler must provide mechanisms that allow an interrupt handler to safely interact with the OS kernel (like unblocking a task).

However, calling OS functions (like unblocking a task or releasing a mutex) from within an interrupt handler presents a potential problem. The OS maintains internal data structures (catalogs of tasks, mutexes, etc.). If an interrupt occurs while the OS kernel is in the middle of updating one of these structures on behalf of a regular task, the handler calling an OS function could find the structure in an inconsistent or corrupt state.

RTOS architectures address this in different ways:

1. Unified Architecture: The OS kernel simply disables interrupts for the short periods it is updating critical internal data structures.
   • Mechanism: When kernel code needs to modify shared kernel data, it briefly disables interrupts globally or partially. Interrupt handlers that trigger during this time are postponed until interrupts are re-enabled.
   • Advantage: Simpler design.
   • Disadvantage: Increases interrupt latency because interrupts are masked while the kernel is working. This can be problematic for systems with very strict latency requirements or high interrupt rates.
2. Segmented Architecture: The OS kernel design minimizes the time spent with interrupts disabled. Instead of having handlers call OS functions directly that might access sensitive structures, the work is delegated.
   • Mechanism: Interrupt handlers might signal a dedicated, high-priority OS handler or a special kernel task. This handler or task runs at a priority higher than any application task but lower than critical hardware interrupt handlers. The kernel handler safely performs the OS-related work (like scheduling decisions, unblocking tasks) using mechanisms that don't require disabling interrupts globally for long periods.
   • Advantage: Minimizes the time spent with interrupts disabled, resulting in lower, more predictable interrupt latency. Better for systems with high interrupt loads or very tight deadlines.
   • Disadvantage: More complex OS kernel design.

Understanding this interaction is crucial when building a kernel, as incorrectly handling shared kernel state between tasks and interrupt handlers is a common source of subtle and hard-to-debug bugs. Mechanisms like x86's System Management Mode (SMM) are also relevant, as they can pause the OS for significant, often unpredictable, durations, which is challenging for RTOS predictability.

Memory Allocation in RTOS

Memory management in an RTOS has different priorities compared to a general-purpose OS.

1. Reliability (No Leaks): RTOS are often used in embedded systems expected to run for years without rebooting. Memory leaks (allocated memory that is no longer needed but not freed) are unacceptable because they would eventually exhaust available memory, leading to failure. For this reason, dynamic memory allocation (allocating and freeing memory while the system is running using functions like malloc/free or new/delete) is often avoided or severely restricted.
   • Preferred Approach: Whenever possible, memory for tasks, queues, buffers, etc., is allocated statically at compile time. This means memory usage is fixed and known before the system even starts, eliminating the possibility of leaks or allocation failures during runtime.
2. Predictability (No Fragmentation, Deterministic Speed):
   • Fragmentation: Dynamic allocation and deallocation can lead to memory fragmentation, where free memory is broken into many small, non-contiguous chunks. Even if the total free memory is sufficient, the OS might fail to allocate a large contiguous block needed by a task.
   • Allocation Speed: Standard dynamic allocation algorithms (like searching a linked list of free blocks) can have unpredictable execution times, potentially taking much longer in the worst case (e.g., searching a long list) than the average case. This non-deterministic speed is unacceptable for real-time guarantees.

Because of these issues, RTOS often use simpler, more predictable memory allocation schemes if dynamic allocation is necessary at all:

• Fixed-Size Blocks: Memory is divided into pools of fixed-size blocks. Allocating memory for a task involves taking a block from the appropriate pool. Deallocating returns the block to the pool. This is simple, fast (finding a free block in a pool is quick), and avoids fragmentation issues related to variable sizes, making the allocation time more predictable.
• Static Allocation: As mentioned, allocating all necessary memory and resources (task stacks, message queues, etc.) at system initialization time is the most reliable approach.

Swapping to disk (using a hard drive as an extension of RAM) is also not used in RTOS. Mechanical disks have extremely long and unpredictable access times compared to CPU operations, making them unsuitable for meeting real-time deadlines.

In summary, memory management in RTOS prioritizes predictability, reliability, and avoiding failure conditions (like leaks or fragmentation preventing allocation) over the flexibility and efficiency of dynamic allocation found in general-purpose OSes.

---